// 归并排序
// 分,归:
// 从中间把要处理的数据拆开
// [4,5,6,3,2,1,8,7]
// [4,5,6,3]
// [2,1,8,7]
// 一直拆到确定拆分的两数组都已排好序(也就是拆成只有1个元素),再进行并
// 并:
// 假设 a b 两个数组都是排好序,将a,b合并
// a = [2,3,6,7] 
// b = [1,4,5,8]
// c = []
// 合并过程
// 谁小就先push进c直到列表结束.

// 并
function merge (arr, l, m, r) {
  let left = []
  let right = []
  // 把原数组的值取出来暂时保存
  // 填充左边数组
  for (let i = l; i < m; i++) {
    left.push(arr[i])
  }

  // 填充右边数组 最左边 l = 0 m = 1 r = 1,所以为等号
  for (let j = m; j <= r; j++) {
    right.push(arr[j])
  }

  let pointL = 0
  let pointR = 0
  let leftLen = left.length
  let rightLen = right.length
  // 在原数组上修改
  let k = l
  while (pointL < leftLen && pointR < rightLen) {
    if (left[pointL] < right[pointR]) {
      arr[k] = left[pointL++]
    } else [
      arr[k] = right[pointR++]
    ]
    k++
  }

  while (pointL < leftLen) {
    arr[k] = left[pointL++]
    k++
  }
  while (pointR < rightLen) {
    arr[k] = right[pointR++]
    k++
  }
}

// 分
function mergeSort (arr, l, r) {
  if (l === r) return
  let m = Math.floor((r - l) / 2) + l
  mergeSort(arr, l, m)
  mergeSort(arr, m + 1, r)
  merge(arr, l, m + 1, r)
}

let arr = [10,9,8,7,6,5,4,3,2,1]
mergeSort(arr, 0, arr.length - 1)
console.log(arr)